package com.cjm.algorithm.babo;

import com.cjm.algorithm.GeneratorUtils;

public class ShellSort {
    public static void main(String[] args) {
        shellSort();
    }
    public static void shellSort() {
        System.out.println("希尔排序\r\n");
        int[] generator = GeneratorUtils.generator();
        shellSort(generator);
        GeneratorUtils.print(generator);
    }
    public static void shellSort(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length;
        int temp;
        for (int step = length / 2; step >= 1 ; step /= 2) {
            for(int i = step; i < length; i++) {
                // 记录下标的值
                temp = arr[i];
                // 记录下标的前一个元素, 它的步长为step
                int j = i - step;
                // j >=0, 拿它与当前值进行比较
                while (j >= 0 && arr[j] > temp) {
                    // 把这个值往前移动一位
                    arr[j + step] = arr[j];
                    // 这个下标往前移动
                    j -= step;
                }
                // 结果不满足, 那么下标值给加回来
                arr[j + step] = temp;
            }
        }
        long l1 = System.currentTimeMillis();
        System.err.println("花了" + (l1 - l) + "ms");
    }
}
